package org.lintcode_Close.Stage1_Easy_50.O3数组与循环;

/**
 * @Auther: qingle
 * @Date: 2024/8/17-15:55
 * @Description:
 * 给一组整数，请将其在原地按照升序排序。使用归并排序，快速排序，堆排序或者任何其他 O(n log n) 的排序算法。
 * @version: 1.0
 */
public class 整数排序nlogn {

	/**
	 * Merge Sort.
	 *
	 * 归并排序利用了分治的思想来对序列进行排序。对一个长为n的待排序的序列，我们将其分解成两个长度为n/2的子序列。
	 * 每次先递归调用函数使两个子序列有序，然后我们再线性合并两个有序的子序列使整个序列有序。
	 *
	 */
	public static void mergeSort(int[] nums) {
		int[] tmp = new int[nums.length];
		mergeSort(nums, tmp, 0, nums.length - 1);
	}

	private static void mergeSort(int[] nums, int[] tmp, int start, int end) {
		if (start >= end) {
			return;
		}

		// divide
		int mid = start + (end - start) / 2;
		mergeSort(nums, tmp, start, mid);
		mergeSort(nums, tmp, mid + 1, end);

		// merge
		int index = start;
		int leftStart = start;
		int rightStart = mid + 1;

		while (leftStart <= mid && rightStart <= end) {
			if (nums[leftStart] <= nums[rightStart]) {
				tmp[index++] = nums[leftStart++];
			} else {
				tmp[index++] = nums[rightStart++];
			}
		}

		while (leftStart <= mid) {
			tmp[index++] = nums[leftStart++];
		}

		while (rightStart <= end) {
			tmp[index++] = nums[rightStart++];
		}

		if (end + 1 - start >= 0)
			System.arraycopy(tmp, start, nums, start, end + 1 - start);
	}


	/**
	 * Quick sort.
	 */
	public static void quickSort(int[] nums) {
		quickSort(nums, 0, nums.length - 1);
	}

	private static void quickSort(int[] nums, int start, int end) {
		if (start >= end) {
			return;
		}

		int left = start;
		int right = end;
		int mid = start + (end - start) / 2;
		int pivot = nums[mid];

		// overview sorted
		while (left <= right) {
			while (left <= right && nums[left] < pivot) {
				left++;
			}

			while (left <= right && nums[right] > pivot) {
				right--;
			}

			// swap left >= p with right <= p to make left <= p right >= p
			if (left <= right) {
				int tmp = nums[left];
				nums[left] = nums[right];
				nums[right] = tmp;
				left++;
				right--;
			}
		}

		quickSort(nums, start, right);
		quickSort(nums, left, end);
	}


	/**
	 * Heap sort.
	 *
	 * 堆排序的思想就是先将待排序的序列建成大根堆，使得每个父节点的元素大于等于它的子节点。此时整个序列最大值即为堆顶元素，我们将其与末尾元素交换，使末尾元素为最大值，然后再调整堆顶元素使得剩下的n−1 个元素仍为大根堆，再重复执行以上操作我们即能得到一个有序的序列。
	 */
	public static void heapSort(int[] nums) {
		// build max heap: for each root node bottom to top and right to left
		for (int i = nums.length / 2; i >= 0; i--) {
			maxHeapify(nums, i, nums.length - 1);
		}

		// swap first and adjust the new root to right position
		for (int i = nums.length - 1; i > 0; i--) {
			int tmp = nums[0];
			nums[0] = nums[i];
			nums[i] = tmp;
			// after each iteration, largest goes to ith, next end at i - 1
			maxHeapify(nums, 0, i - 1);
		}
	}

	private static void maxHeapify(int[] nums, int start, int end) {
		int parent = start;

		// top to bottom
		while (parent <= end) {
			int left = parent * 2 + 1;
			int right = parent * 2 + 2;
			int child = -1;

			if (left <= end && right <= end) {
				// large value as swap candidate
				child = (nums[left] >= nums[right] ? left : right);
			} else if (left <= end) {
				child = left;
			} else {
				return;
			}

			// max heap root >= left && root >= right
			if (nums[parent] >= nums[child]) {
				return;
			}

			// swap
			int tmp = nums[parent];
			nums[parent] = nums[child];
			nums[child] = tmp;

			// update parent index
			parent = child;
		}
	}

	public static void main(String[] args) {
		int[] arr = { 3, 2, 1, 4, 5 };
//		mergeSort(arr);
//		quickSort(arr);
		heapSort(arr);
		for (int i : arr) {
			System.out.print(i + " ");
		}
	}
}
